package agent;

import instanceXMLParser.CellLogicalState;
import instanceXMLParser.Instance;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.alg.FloydWarshallShortestPaths;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.paukov.combinatorics.Factory;
import org.paukov.combinatorics.Generator;
import org.paukov.combinatorics.ICombinatoricsVector;

import aima.core.agent.Action;
import aima.core.agent.impl.DynamicAction;
import aima.core.agent.impl.NoOpAction;
import core.VacuumEnvironment.LocationState;

public class VacuumAgentSolverHeuristicKBest extends AbstractVacuumSolver
implements Runnable {

	DirectedGraph<Integer, DefaultEdge> board = new DefaultDirectedGraph<Integer, DefaultEdge>(
			DefaultEdge.class);

	public static double suckCost = 1;
	int m, n;
	double ResidualEnergy;
	List<Integer> AllTargetCell = new ArrayList<Integer>();
	CellLogicalState[][] boardState;// as argument from the environmentMap
	Point agentStartPosition;
	Point basePoint;

	List<Integer> targetCells = new ArrayList<Integer>();
	Map<Integer, Integer> dirtyAmounts;

	final int INFDIST = 1000;

	public int KBEST = 5;

	int solutionNumCleaned;

	double solutionCost;

	List<Integer> solutionPath = new ArrayList<Integer>();

	List<Integer> completeSolutionPath = new ArrayList<Integer>();

	// FloydWarshallShortestPaths<Integer, DefaultEdge> shortesTpath;

	List<Action> solution;

	int[][] distances;

	public VacuumAgentSolverHeuristicKBest(int KBEST, int n, int m,
			List<Integer> AllTargetCells, CellLogicalState[][] partialBoard,
			Point agentStartPos, Point basePoint, double energy,
			Map<Integer, Integer> dirtyAmounts) {
		this.KBEST = KBEST;
		id = "kbest" + KBEST;
		this.n = n;
		this.m = m;
		this.AllTargetCell = AllTargetCells;
		this.boardState = partialBoard;
		this.agentStartPosition = agentStartPos;
		this.basePoint = basePoint;
		this.ResidualEnergy = energy;

		this.dirtyAmounts=dirtyAmounts;
	}

	public VacuumAgentSolverHeuristicKBest() {
	}

	private int shortestDistance(Integer i, Integer j) {
		if (i == j) {
			return 0;
		}

		Integer res = distances[i][j];
		if (res == -1) {
			List<DefaultEdge> path = DijkstraShortestPath.findPathBetween(
					board, i, j);
			if (path == null) {
				distances[i][j] = INFDIST;
			} else {
				distances[i][j] = path.size();
			}
		}
		return distances[i][j];

	}

	public void solve(String path) {
		/*
		 * long startTime = System.currentTimeMillis();
		 * 
		 * instance = new Instance(); instance.buildINstanceJDom(path); //
		 * instance.toString(); board = createGraph();
		 * 
		 * 
		 * // shortesTpath = new FloydWarshallShortestPaths<Integer,
		 * DefaultEdge>( board); targetCells = listAllreachableTarget(); //
		 * System.out.println("Target cells: " + targetCells); isSolvable();
		 * 
		 * calculateBestSolution();
		 * 
		 * // validate cost int cost = 0; for (int i = 0; i <
		 * solutionPath.size() - 1; i++) { if
		 * (targetCells.contains(solutionPath.get(i))) { cost +=
		 * instance.getActionCosts().get("suck");// suck operation } cost +=
		 * shortestDistance(solutionPath.get(i), solutionPath.get(i + 1)); } //
		 * System.out.println("costo soluzione = " + solutionPath + " =" +
		 * cost);
		 * 
		 * completeSolutionPath = buildCompletePath();
		 * 
		 * solution = new ArrayList<Action>(); buildSolutionFromVertexPath();
		 * 
		 * long estimatedTime = System.currentTimeMillis() - startTime;
		 * 
		 * // System.out.println("\nelapsed time " + (double) (estimatedTime) /
		 * 1000 // + " seconds");
		 */
	}

	public void solve() {
		long startTime = System.currentTimeMillis();

		// instance.toString();
		board = createGraph();

		// shortesTpath = new FloydWarshallShortestPaths<Integer,
		// DefaultEdge>(board);

		distances = new int[n * m][n * m];
		for (int i = 0; i < n * m; i++) {
			for (int j = 0; j < n * m; j++) {
				distances[i][j] = -1;
			}
		}

		targetCells = listAllreachableTarget();
		// System.err.println("Target cells: " + targetCells);

		calculateBestSolution();

		// validate cost
		int cost = 0;
		for (int i = 0; i < solutionPath.size() - 1; i++) {
			if (targetCells.contains(solutionPath.get(i))) {
				cost += suckCost;// suck operation
			}
			cost += shortestDistance(solutionPath.get(i),
					solutionPath.get(i + 1));
		}
		// System.out.println("costo soluzione = " + solutionPath + " =" +
		// cost);

		completeSolutionPath = buildCompletePath();

		solution = new ArrayList<Action>();

		buildSolutionFromVertexPath();

		// System.err.println(completeSolutionPath.size());

		long estimatedTime = System.currentTimeMillis() - startTime;

		// System.out.println("\nelapsed time " + (double) (estimatedTime) /
		// 1000
		// + " seconds");
	}

	public void solveFromInstance(Instance i) {
		/*
		 * long startTime = System.currentTimeMillis();
		 * 
		 * instance = i; // instance.toString(); board = createGraph();
		 * //shortesTpath = new FloydWarshallShortestPaths<Integer,
		 * DefaultEdge>(board); targetCells = listAllreachableTarget(); //
		 * System.out.println("Target cells: " + targetCells); isSolvable();
		 * 
		 * calculateBestSolution();
		 * 
		 * completeSolutionPath = buildCompletePath();
		 * 
		 * solution = new ArrayList<Action>(); buildSolutionFromVertexPath();
		 * 
		 * long estimatedTime = System.currentTimeMillis() - startTime;
		 * 
		 * // System.out.println("\nelapsed time " + (double) (estimatedTime) /
		 * 1000 // + " seconds");
		 */

	}

	private List<Integer> buildCompletePath() {
		List<Integer> completePath = new ArrayList<Integer>();

		for (int pathLoc = 0; pathLoc < solutionPath.size() - 1; pathLoc++) {

			List<DefaultEdge> tempStep;
			DijkstraShortestPath<Integer, DefaultEdge> pathFinder = new DijkstraShortestPath<Integer, DefaultEdge>(
					board, solutionPath.get(pathLoc),
					solutionPath.get(pathLoc + 1));
			tempStep = pathFinder.getPathEdgeList();

			// System.out.println("bestpath between "+bestPermutation.get(pathLoc)+" and "+bestPermutation.get(pathLoc+1));
			for (DefaultEdge defaultEdge : tempStep) {

				if (completePath.size() == 0
						|| !completePath.get(completePath.size() - 1).equals(
								(Integer) board.getEdgeSource(defaultEdge)))
					completePath
					.add((Integer) board.getEdgeSource(defaultEdge));

				completePath.add((Integer) board.getEdgeTarget(defaultEdge));

				// System.out.print((Integer)directedGraph.getEdgeSource(defaultEdge)+" "+(Integer)
				// directedGraph.getEdgeTarget(defaultEdge)+" " );

			}
			// System.out.println();

		}

		return completePath;
	}

	// two vertex at position i and i+1 are such that
	// abs(vertex(i),vertex(i+1))=1(left or right) or instance.size();(up and
	// down)
	private void buildSolutionFromVertexPath() {
		List<Integer> pulite = new ArrayList<Integer>();

		for (int i = 0; i < completeSolutionPath.size() - 1; i++) {
			int from = completeSolutionPath.get(i);
			int to = completeSolutionPath.get(i + 1);
			int diffX = from / m - to / m;
			int diffY = from % m - to % m;
			if (targetCells.contains(from) && !pulite.contains(from)
					&& solutionPath.contains(from)) {
				for(int s=0;s<dirtyAmounts.get(from);s++){
					solution.add(new DynamicAction("suck"));
				}
				pulite.add(from);
			}
			if (diffY == 1) {// left
				solution.add(new DynamicAction("left"));
			} else if (diffY == -1) {// right
				solution.add(new DynamicAction("right"));
			} else if (diffX == 1) {// up
				solution.add(new DynamicAction("up"));
			} else if (diffX == -1) {// down
				solution.add(new DynamicAction("down"));

			}

		}// for
		if (boardState[basePoint.x][basePoint.y].getLocState() == LocationState.Dirty) {
			solution.add(new DynamicAction("suck"));
		}
		solution.add(NoOpAction.NO_OP);

		// System.out.println("\nSOLUZIONE:");
		for (Action soluAction : solution) {
			String name = ((DynamicAction) soluAction).getName();
			// System.out.print(name + " ");
		}
		// System.out.println();
	}

	/**
	 * Calcola iterativamente blocchi di K nodi migliori, e lio mette nella
	 * soluzione.
	 * 
	 */

	private void calculateBestSolution() {
		double solutionCost = 0;


		List<Integer> daPulire = new ArrayList<Integer>();
		daPulire.addAll(targetCells);

		solutionPath.add(0,
				RowMajIdx(agentStartPosition.x, agentStartPosition.y, m));

		// finchè ho energia o ci sono ancora celle da pulire
		// Create the initial vector

		boolean end = false;
		while (solutionCost < ResidualEnergy && daPulire.size() > 0 && !end) {
			// System.out.println("Gruppo nuovo");
			ICombinatoricsVector<Integer> initialVector = Factory
					.createVector(daPulire);
			// provo gruppi dal piu grande al piu piccolo
			boolean continueSearch = true;
			List<Integer> bestGruppoIntermedio = new ArrayList<Integer>();
			for (int k = KBEST; k > 0 && continueSearch; k--) {
				// Create a simple combination generator to generate
				// K-combinations of the initial vector
				Generator<Integer> gen = Factory
						.createSimpleCombinationGenerator(initialVector, k);

				double minSizeCostStep = Integer.MAX_VALUE;
				for (ICombinatoricsVector<Integer> combination : gen) {
					List<Integer> combinazione = combination.getVector();
					// System.out.println(combinazione);
					double currCost = shortestDistance(
							solutionPath.get(solutionPath.size() - 1),
							combinazione.get(0));
					// currCost += combinazione.size() * suckCost;//old
					for (int pathLoc = 0; pathLoc < combination.getSize() - 1; pathLoc++) {
						currCost += dirtyAmounts.get(combinazione.get(pathLoc));
						currCost += shortestDistance(combinazione.get(pathLoc),
								combinazione.get(pathLoc + 1));
					}
					currCost+=dirtyAmounts.get(combinazione.get(combinazione.size() - 1));// ulktima
					// cella
					// da
					// pulire

					// affinchè sia uno step ammissibile bisogna controllare
					// che rimanga energia
					// per ritornare alla base
					int distanzaBase = shortestDistance(
							combinazione.get(combinazione.size() - 1),
							RowMajIdx(basePoint.x, basePoint.y, m));// dall'ultimo
					// nodo
					// dirty
					// pulito
					// alla
					// base
					// di
					// nuovo
					if (solutionCost + currCost + distanzaBase <= ResidualEnergy) {// step
						// ammissibile
						// (dopo
						// aver
						// visitato combinazione node riesco
						// a tornare alla base
						if (currCost < minSizeCostStep) {
							// step ammissibile e migliore di quello trovato
							// prima
							minSizeCostStep = currCost;
							bestGruppoIntermedio.clear();
							bestGruppoIntermedio.addAll(combinazione);
							// System.out
							// .println("nuova combo migliore "
							// + combinazione + "costo "
							// + minSizeCostStep);
						}
					}

				}// combinazioni k<=KBEST corrente

				if (bestGruppoIntermedio.size() > 0) {
					// trovato un gruppo di dim <=KBEST ammissibile, posso
					// smettere di cercare
					// System.out
					// .println("gruppo buono trovato k massimo possibile valuta possibilità di abbassare il threshold KBEST");
					// System.out.println("DIM =" + k);
					continueSearch = false;
					solutionPath.addAll(bestGruppoIntermedio);
					daPulire.removeAll(bestGruppoIntermedio);
					// System.out.println("nuovo target cell =" + daPulire);
					solutionCost += minSizeCostStep;
				}

			}// for KBEST

			if (bestGruppoIntermedio.size() <= 0) {
				// solutionPath.add(RowMajIdx(instance.getBasePos().getX(),instance.getBasePos().getY(),
				// instance.getSize()));
				// System.out.println("finito");
				end = true;
			}

		}
		solutionPath.add(RowMajIdx(basePoint.x, basePoint.y, m));
		// System.out.println("path complete =" + solutionPath);

	}

	// controlla se le celle sporche sono raggiungibili: hai abbastanza energia
	// per raggiungerle?(ammesso che esista un path)
	public ArrayList<Integer> listAllreachableTarget() {
		ArrayList<Integer> target = new ArrayList<Integer>();
		for (int i = 0; i < AllTargetCell.size(); i++) {
			// System.err.println(" RowMajIdx(agentStartPosition.x, agentStartPosition.y, m) :"
			// + RowMajIdx(agentStartPosition.x, agentStartPosition.y, m));
			if (shortestDistance(AllTargetCell.get(i),
					RowMajIdx(agentStartPosition.x, agentStartPosition.y, m)) +dirtyAmounts.get(AllTargetCell.get(i)) < ResidualEnergy) {
				target.add(AllTargetCell.get(i));

			}
		}
		return target;
	}

	public static int RowMajIdx(int x, int y, int size) {
		return x * size + y;
	}

	private DirectedGraph<Integer, DefaultEdge> createGraph() {
		DirectedGraph<Integer, DefaultEdge> g = new DefaultDirectedGraph<Integer, DefaultEdge>(
				DefaultEdge.class);

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (boardState[i][j].getLocState() != LocationState.Obstacle)
					g.addVertex(new Integer(RowMajIdx(i, j, m)));

		int i = 0;
		int j = 0;
		for (int vertex : g.vertexSet()) {
			i = vertex / m;
			j = vertex % m;
			if (g.containsVertex(RowMajIdx(i + 1, j, m)) && i != n - 1)
				g.addEdge(vertex, RowMajIdx(i + 1, j, m));
			if (g.containsVertex(RowMajIdx(i - 1, j, m)) && i != 0)
				g.addEdge(vertex, RowMajIdx(i - 1, j, m));
			if (g.containsVertex(RowMajIdx(i, j + 1, m)) && j != m - 1)
				g.addEdge(vertex, RowMajIdx(i, j + 1, m));
			if (g.containsVertex(RowMajIdx(i, j - 1, m)) && j != 0)
				g.addEdge(vertex, RowMajIdx(i, j - 1, m));
		}

		// rendo le celle ostacolo irraggiungibili. nessuna connnessione in
		// uscita ne in entrata
		// escludo gli angoli. Quando da una cella dentro il bordo creo un arco
		// automaticamente creo l'arco opposto
		// for (int i = 0; i < n; i++) {
		// for (int j = 0; j < m; j++) {
		// // celle dentro il bordo esterno
		// if (boardState[i][j].getLocState() != LocationState.Obstacle) {
		// if (i > 0 && i < n - 1) {
		// if (j > 0 && j < m - 1) {
		// if (boardState[i - 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i - 1, j, m));
		// }
		//
		// if (boardState[i + 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i + 1, j, m));
		// }
		//
		// if (boardState[i][j + 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j + 1, m));
		// }
		//
		// if (boardState[i][j - 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j - 1, m));
		// }
		// }
		// }
		//
		// // prima riga senza angoli
		// if (i == 0) {
		// if (j > 0 && j < m - 1) {
		// // if (boardState[i + 1][j].getLocState() != LocationState.Obstacle)
		// {
		// // g.addEdge(RowMajIdx(i, j, m),
		// // RowMajIdx(i + 1, j, m));
		// // }
		//
		// if (boardState[i][j + 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j + 1, m));
		// }
		//
		// if (boardState[i][j - 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j - 1, m));
		// }
		// }
		// }
		//
		// // ultimariga senza angoli
		// if (i == n - 1) {
		// if (j > 0 && j < m - 1) {
		// // if (boardState[i - 1][j].getLocState() != LocationState.Obstacle)
		// {
		// // g.addEdge(RowMajIdx(i, j, m),
		// // RowMajIdx(i - 1, j, m));
		// // }
		//
		// if (boardState[i][j + 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j + 1, m));
		// }
		//
		// if (boardState[i][j - 1].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i, j - 1, m));
		// }
		// }
		// }
		//
		// // prima colonna senza angoli
		// if (j == 0) {
		// if (i > 0 && i < n - 1) {
		// if (boardState[i - 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i - 1, j, m));
		// }
		//
		// if (boardState[i + 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i + 1, j, m));
		// }
		//
		// // if (boardState[i][j + 1].getLocState() != LocationState.Obstacle)
		// {
		// // g.addEdge(RowMajIdx(i, j, m),
		// // RowMajIdx(i, j + 1, m));
		// // }
		//
		// }
		// }
		//
		// // ultima colonna senza angoli
		// if (j == m - 1) {
		// if (i > 0 && i < n - 1) {
		// if (boardState[i - 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i - 1, j, m));
		// }
		//
		// if (boardState[i + 1][j].getLocState() != LocationState.Obstacle) {
		// g.addEdge(RowMajIdx(i, j, m),
		// RowMajIdx(i + 1, j, m));
		// }
		//
		// // if (boardState[i][j - 1].getLocState() != LocationState.Obstacle)
		// {
		// // g.addEdge(RowMajIdx(i, j, m),
		// // RowMajIdx(i, j - 1, m));
		// // }
		//
		// }
		// }
		//
		// }// obstacle
		// } // forj
		// }// fori
		//
		// for (int i = 0; i < n*n; i++) {
		// for (int j = 0; j < m*m; j++) {
		// if (g.containsEdge(i, j)) {
		// g.addEdge(j, i);
		// }
		// }
		// }

		return g;
	}

	public static void main(String[] args) {
		VacuumAgentSolverHeuristicKBest agent = new VacuumAgentSolverHeuristicKBest();
		agent.solve("instance_EXAMPLE.xml");
	}

	public String getId() {
		return id;
	}

	@Override
	public void run() {
		this.solve();

	}

	public List<Action> getSolution() {
		return solution;
	}

}
